package demo.DataStrucAndAlgo.AlgorithmOfTen;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/8-08-08-18:47
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen       贪心算法
 */
/*
贪心算法
   在对问题求解时，每一步都选最优的结果，这些每步最优结果汇集成问题的最终结果。但这个结果不一定是最优结果
   因为每一步可能存在多个最优解，贪心算法只会按照顺序选择其中一个
 */
/*
    e.g.
        存在下表中的站点1~5，每个站点对应不同的覆盖城市，需要选择最少的站点，覆盖全部城市
        站点                            覆盖城市
        K1                             北京、上海、天津
        K2                             广州、北京、深圳
        K3                             成都、上海、杭州
        K4                             上海、天津
        K5                             杭州、大连
*/
/*
    算法分析：
        每步中的最优解有可能不止一个，比如说：allAreas中只剩杭州时，K3和K5交集大小都为1，按照顺序取得的策略
        贪心算法会选择K3，而不是K5.如果选择K5花的钱比K3少时，贪心算法获得的结果就不算最优了，但它一定满足都覆盖
        根据贪心算法的原理，我们需要一个maxKey指针和Key指针，还需要一个集合allAreas用于存储全部城市。每次循环key指针从K1指到K5
        而maxKey指针用于指向循环中，覆盖城市与全部城市交集最大的Kn站点（取得每步的最优解），当5个站点都循环完成后，需要把maxKey
        指向的站点加入到一个专门存储解的集合selects中，同时要删除allAreas中Kn覆盖的城市部分，并重置maxKey，
        再进行循环。直到allAreas集合大小为0时结束。
*/
public class greedyAlgorithm {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> broad = new HashMap<>();                 //存储所有站点及城市
        HashSet<String> place1 = new HashSet<>();
        place1.add("北京");
        place1.add("上海");
        place1.add("天津");
        broad.put("K1",place1);
        HashSet<String> place2 = new HashSet<>();
        place2.add("北京");
        place2.add("广州");
        place2.add("深圳");
        broad.put("K2",place2);
        HashSet<String> place3 = new HashSet<>();
        place3.add("成都");
        place3.add("上海");
        place3.add("杭州");
        broad.put("K3",place3);
        HashSet<String> place4 = new HashSet<>();
        place4.add("上海");
        place4.add("天津");
        broad.put("K4",place4);
        HashSet<String> place5 = new HashSet<>();
        place5.add("杭州");
        place5.add("大连");
        broad.put("K5",place5);

        HashSet<String> allAreas = new HashSet<>();
        allAreas.addAll(place1);
        allAreas.addAll(place2);
        allAreas.addAll(place3);
        allAreas.addAll(place4);
        allAreas.addAll(place5);

        System.out.println(allAreas);
        HashSet<String> selects = new HashSet<>();        //存储每次选取的站点
        String maxKey = null;
        while(allAreas.size()> 0){

            int key = 0;            //统计每个站点和allAreas的交集城市个数
            for (String s : broad.keySet()) {
                int count = 0;
                for (String s1 : broad.get(s)) {
                    if(allAreas.contains(s1)){
                        count++;
                    }
                }
                if(count > key){          //获取最大交集的站点，
                    key = count;
                    maxKey = s;
                }
            }
            selects.add(maxKey);
            for (String s : broad.get(maxKey)) {
                if(allAreas.contains(s)){
                    allAreas.remove(s);
                }
            }
            //allAreas.removeAll(broad.get(maxKey));
        }
        System.out.println(selects);
    }
    public String intToRoman(int num) {
        // 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中，并且按照阿拉伯数字的大小降序排列
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder stringBuilder = new StringBuilder();
        int index = 0;
        while (index < 13) {
            // 特别注意：这里是等号
            while (num >= nums[index]) {
                stringBuilder.append(romans[index]);
                num -= nums[index];
            }
            index++;
        }
        return stringBuilder.toString();
    }

}
